#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

/**
 *
 *本文章是对企业面试题库LeetcodeTop的补充，汇总那些在Leetcode上找不到的面试高频题。
首先引用一些考到本题的面经原文描述
0-12共13个数构成一个环，从0出发，每次走1步，走n步回到0共有多少种走法（2020.09 字节跳动-广告-后端）[1]
0-8组成一个圆环，从0出发，每次可以逆时针和顺时针走，走n步能回到0有多少种情况（2020.09 字节跳动-people-后端）[2]
0~9的环，从0出发，N步后能否走回0。（2020.07 字节跳动-电商-后端）[3]
圆环回原点问题 (2020.08 字节跳动-飞书-后端)[4]
题目描述

圆环上有10个点，编号为0~9。从0点出发，每次可以逆时针和顺时针走一步，问走n步回到0点共有多少种走法。
输入: 2
输出: 2
解释：有2种方案。分别是0->1->0和0->9->0

题目分析
本题考察的是动态规划。
如果你之前做过leetcode的70题爬楼梯，则应该比较容易理解：走n步到0的方案数=走n-1步到1的方案数+走n-1步到9的方案数。
因此，若设dp[i][j]为从0点出发走i步到j点的方案数，则递推式为：
图片
ps:公式之所以取余是因为j-1或j+1可能会超过圆环0~9的范围
 * */
//TODO 没看懂
void backToOrign(int size, int n) {

    //这个dp表示若设dp[i][j]为从0点出发走i步到j点的方案数
    //等于前一步的方法数
    //走n步到0的方案数=走n-1步到1的方案数+走n-1步到9的方案数。
    vector<vector<int>> dp(n + 1, vector<int>(size, 0));
    dp[0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < size; ++j) {
            //这个应该是从左边过来和从右边过来的
            dp[i][j] = dp[i - 1][(j - 1 + size) % size] + dp[i - 1][(j + 1) % size];
        }
    }

    cout << dp[n][0];


}


#define LENGTH 10
#define N 2

unsigned int circle2ori_point() {
    int dp[N + 1][LENGTH]{{0}};
    dp[0][0] = 1;
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < LENGTH; j++) {
            dp[i][j] = dp[i - 1][(j - 1 + LENGTH) % LENGTH] + dp[i - 1][(j + 1) % LENGTH];
        }
    }
    cout << dp[N][0];
    return dp[N][0];
}